package E_2024;

import java.util.ArrayList;
import java.util.List;

/*
    二叉树也可以用数组来存储，给定一个数组，树的根节点的值存储在下标1，
    对于存储在下标N的节点，它的左子节点和右子节点分别存储在下标2N和2N+1，并且我们用值-1代表一个节点为空。
    给定一个数组存储的二叉树，试求从根节点到最小的叶子节点的路径，路径由节点的值组成。
输入描述
    输入一行为数组的内容，数组的每个元素都是正整数，元素间用空格分隔。
    注意第一个元素即为根节点的值，即数组的第N个元素对应下标N，下标0在树的表示中没有使用，所以我们省略了。
    输入的树最多为7层。
输出描述
    输出从根节点到最小叶子节点的路径上，各个节点的值，由空格分隔，用例保证最小叶子节点只有一个。
示例 1：
    输入
    3 5 7 -1 -1 2 4
    输出
    3 7 2
    说明
    最小叶子节点的路径为3 7 2
示例 2：
    输入
    5 9 8 -1 -1 7 -1 -1 -1 -1 -1 6
    输出
    5 8 7 6
    说明
    最小叶子节点的路径为5 8 7 6࿰
 */
public class E_200_4 {
    public static void main(String[] args) {
        ans(new int[]{3,5,7,-1,-1,2,4});
        ans(new int[]{5,9,8,-1,-1,7,-1,-1,-1,-1,-1,6});
        ans(new int[]{5,9,8,1,-1,7,-1,1,-1,-1,-1,6});
    }
    public static void ans(int[] arr){
        // 计算树结构最后一层从哪个坐标开始，第一层坐标为0，不用考虑，直接从第2层开始
        // 第2层起始坐标为1
        int k = 1;
        // i为当前所在的层级，第0层不需要考虑
        for (int i = 1; true; i++) {
            // 第i层所有值的数量
            int x = 1 << i;
            // 当前层总数+历史数大于数组长度时说明不会有下一层级，返回当前层起始位
            if (k + x >= arr.length) {
                break;
            }
            k += x;
        }
        // 获取当前层最小的值下标
        int index = 0;
        int num = Integer.MAX_VALUE;
        for (int i = k; i < arr.length; i++) {
            if (num > arr[i] && arr[i] >= 0) {
                index = i;
                num = arr[i];
            }
        }
        List<Integer> list = new ArrayList<>();
        // 由于题中计算位从1开始，需要下标+1
        index ++;
        while (index > 0) {
            list.add(arr[index -1]);
            index = index >> 1;
        }
        // 这里需要将数组反转输出
        System.out.println(list);
    }
}
